package com.leetcode.No0743;

import org.junit.Test;

import java.util.*;

/**
 * @program: leetcode
 * @description: 网络延迟时间
 * @author: wangzhihua
 * @date: 2021-08-08
 */
public class Solution01 {

	@Test
	public void test01() {
		int[][] times = new int[][]{{2,1,1},{2,3,1},{3,4,1}};
		System.out.println(networkDelayTime(times, 4, 2));
	}

	@Test
	public void test02() {
		int[][] times = new int[][]{{1,2,1}};
		System.out.println(networkDelayTime(times, 2, 1));
	}

	@Test
	public void test03() {
		int[][] times = new int[][]{{1,2,1}};
		System.out.println(networkDelayTime(times, 2, 2));
	}

	public int networkDelayTime(int[][] times, int n, int k) {
		if (n == 1) {
			return 0;
		}
		HashMap<Integer, List<CompositeKey>> timeInfoMap = new HashMap<>();
		for (int[] time : times) {
			List<CompositeKey> list = timeInfoMap.computeIfAbsent(time[0], k1 -> new ArrayList<>());
			list.add(new CompositeKey(time[0], time[1], time[2]));
		}
		int[] distance = new int[n + 1];
		for (int i = 1; i <= n; ++i) {
			distance[i] = Integer.MAX_VALUE;
		}
		distance[k] = 0;
		LinkedList<Integer> candidateList = new LinkedList<>();
		candidateList.add(k);
		while(candidateList.size() > 0) {
			int origin = candidateList.pollFirst();
			List<CompositeKey> targetList = timeInfoMap.get(origin);
			if (targetList == null) {
				continue;
			}
			for (CompositeKey item : targetList) {
				if (distance[item.end] > distance[item.start] + item.val) {
					distance[item.end] = distance[item.start] + item.val;
					candidateList.add(item.end);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			if (distance[i] == Integer.MAX_VALUE) {
				return -1;
			}
			ans = Math.max(ans, distance[i]);
		}
		return ans;
	}

	private class CompositeKey {
		int start;
		int end;
		int val;

		public CompositeKey(int start, int end, int val) {
			this.start = start;
			this.end = end;
			this.val = val;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (o == null || getClass() != o.getClass()) return false;
			CompositeKey that = (CompositeKey) o;
			return start == that.start &&
					end == that.end &&
					val == that.val;
		}

		@Override
		public int hashCode() {
			return Objects.hash(start, end, val);
		}
	}

}
